import common.ListNode;

/**
 * 82. Remove Duplicates From Sorted List II 删除排序链表中的重复元素 II
 * https://lleetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
 */
class RemoveDuplicatesFromSortedListII {
    /**
     * 方法：双指针遍历，遇到重复值时跳过所有重复节点
     * 
     * Args:
     *      head: 排序链表的头节点
     * 
     * Returns: 
     *      删除所有重复元素后的链表头节点
     * 
     * Time: O(n), 其中n为链表长度，需要遍历一次链表
     * 
     * Space: O(1), 只使用常数额外空间
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null){
            int val = cur.next.val;
            if(val == cur.next.next.val){// 后两个节点值相同
                while(cur.next != null && val == cur.next.val){
                    // 值等于 val 的节点全部删除
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}